<?php

/**
 *
 * Class Solution
 */
class Solution {

    /**
     * @param Integer $n
     * @return String[]
     */
    function generateParenthesis($n) {
        /**
         * 题解思路
         * n个括号的对数，代表一共有n个左括号 "(" 和 n个右括号 ")"
         * 等于是做组合
         * 但是左括号和右括号是有限制的，右括号在括号关闭之前是不可以单独出现的
         * 在限制之下做出组合即可
         */
        return $this->generateParenthesisBy($n,$n,['']);
    }

    /**
     * 生成可能性
     * @param $leftRemain
     * @param $rightRemain
     * @param $arr
     *
     * @return array
     */
    function generateParenthesisBy($leftRemain,$rightRemain,$arr){

            if($rightRemain==0){
                return $arr;
            }elseif($leftRemain==0){
                $tmp=[];
                foreach($arr as $item){
                    $tmp[]=$item.')';
                }
                return $this->generateParenthesisBy($leftRemain,$rightRemain-1,$tmp);
            }elseif($rightRemain<=$leftRemain){
                $tmp=[];
                foreach($arr as $item){
                    $tmp[]=$item.'(';
                }
                return $this->generateParenthesisBy($leftRemain-1,$rightRemain,$tmp);
            }elseif($leftRemain>0){
                $tmp=[];
                foreach($arr as $item){
                    $tmp[]=$item.'(';
                }
                $arr1= $this->generateParenthesisBy($leftRemain-1,$rightRemain,$tmp);

                $tmp=[];
                foreach($arr as $item){
                    $tmp[]=$item.')';
                }
                $arr2= $this->generateParenthesisBy($leftRemain,$rightRemain-1,$tmp);
                return array_merge($arr1,$arr2);
            }

            return $arr;
    }

    function test($n,$rightArr){
        $arr=$this->generateParenthesis($n);
        foreach($rightArr as $v){
            if(!in_array($v,$arr)) return false;
        }
        return true;
    }

    function debug(){
        return $this->generateParenthesis(3);
    }
}